#include <cstdio>
#include <algorithm>

using std::swap;
using std::sort;

const int maxn=10005;
const int inf=0x3f3f3f3f;
const int offset=1000;

struct iostream{
	const static int bufsiz=150000;
	FILE *i,*o;
	char outbuf[bufsiz];int outpos;
	iostream(FILE *i=stdin,FILE *o=stdout):i(i),o(o),outpos(0){}
	inline iostream& operator >> (char &c){
		static char buf[bufsiz];
		static int pos=bufsiz,end=bufsiz;
		if(pos==end) end=fread(buf,1,bufsiz,i),pos=0;
		if(pos==end) c=EOF;
		else c=buf[pos++];
		return *this;
	}
	template <typename T> inline iostream& operator >> (T &r){
		char c;bool f=0;
		for(*this>>c;c>'9'||c<'0';*this>>c) if(c=='-') f=1;
		for(r=0;c<='9'&&c>='0';*this>>c) r=r*10+c-'0';
		if(f) r=-r;
		return *this;
	}
	inline iostream& operator << (const char &c){
		outbuf[outpos++]=c;
		if(outpos==bufsiz) fwrite(outbuf,1,bufsiz,o),outpos=0;
		return *this;
	}
	template <typename T> inline iostream& operator << (T r){
		static int sta[50];int head=0;
		if(r<0) {*this<<'-';r=-r;}
		while(r){sta[head++]=r%10,r/=10;}
		if(!head) *this<<'0';
		while(head--) *this<<(char)(sta[head]+'0');
		return *this;
	}
	~iostream(){
		fwrite(outbuf,outpos,1,o);
	}
};

struct Point{
	int x,y,id;
	const bool operator < (const Point &p) const{return x>p.x||x==p.x&&y>p.y;}
};
struct Edge{
	int u,v,w;
	const bool operator < (const Edge &e) const{return w<e.w;}	
	Edge(){}
	Edge(const int &u,const int &v,const int &w):u(u),v(v),w(w){}
};
struct Pair{
	int w,p;
	const bool operator < (const Pair &p) const{return w<p.w;}
};

Point p[maxn];Edge e[maxn*8];int en;
Pair bit[2005];
int n;
int fa[maxn];
iostream io(stdin,stdout);

template <typename T> void update(T &x, T y){if(y<x) x=y;}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
inline int kruskal(int k){
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(e,e+en);
	int ans=0;
	for(int i=0;i<en;i++){
		if(find(e[i].u)!=find(e[i].v)){
			fa[find(e[i].u)]=find(e[i].v);
			k--;
			if(!k){
				ans=e[i].w;
				break;
			}
		}
	}
	return ans;
}

inline int lowbit(const int &x){return x&(-x);}
inline Pair check(int x){
	Pair ans=bit[x];
	for(;x<2005;x+=lowbit(x)) update(ans,bit[x]);
	return ans;
}
inline void insert(int x,const Pair &p){
	for(;x>0;x-=lowbit(x)) update(bit[x],p);
}
inline void solve(){
	for(int i=0;i<2005;i++) bit[i]=(Pair){inf,-1};
	sort(p,p+n);
	for(int i=0;i<n;i++){
		int cur=p[i].x+p[i].y;
		Pair tar=check(p[i].y-p[i].x+offset);
		if(tar.p!=-1)
			e[en++]=Edge(p[i].id,tar.p,tar.w-cur);
		insert(p[i].y-p[i].x+offset,(Pair){cur,p[i].id});
	}
}



int main(){
	int k;

	freopen("3241.in","r",stdin);
	freopen("3241.out","w",stdout);

	io>>n>>k;
	for(int i=0;i<n;i++) io>>p[i].x>>p[i].y,p[i].id=i+1;
	k=n-k;
	solve();
	for(int i=0;i<n;i++) swap(p[i].x,p[i].y);
	solve();
	for(int i=0;i<n;i++) p[i].x=-p[i].x;
	solve();
	for(int i=0;i<n;i++) swap(p[i].x,p[i].y);
	solve();

	io<<kruskal(k)<<'\n';

	return 0;
}